//
// Created by lanlu on 2025/8/7.
//

#include <vector>
#include <stack>
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
    {
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root)
    {
        vector<int> result;
        // 栈中存储节点
        stack<TreeNode *> s;
        TreeNode *cur = root;
        // 当节点仍有值 或 栈中还有元素时 继续循环
        while (cur != nullptr || !s.empty())
        {
            // 遍历所有左孩子 依次压入栈中
            while (cur != nullptr)
            {
                s.push(cur);
                // 在入栈时存入到结果集中
                result.push_back(cur->val);
                cur = cur->left;
            }

            // 弹栈 处理右孩子
            cur = s.top();
            s.pop();
            cur = cur->right;
        }
        return result;
    }
};
